package algocasts;

public class P118_Fibonacci {
    // Time: O(2^n)  Space: O(n)
    public int fib_Recursion(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        return fib_Recursion(n - 1) + fib_Recursion(n - 2);
    }

    // Time: O(n)  Space: O(n)
    public int fib_dp(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }

    // Time: O(n)  Space: O(1)
    public int fib_dpO1(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        int first = 0, second = 1;
        for (int i = 2; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }


    public static void main(String[] args) {
        System.out.println(new P118_Fibonacci().fib_Recursion(5));
    }
}
